In multiprocessing, processors may employ multithreading logic to execute a plurality of threads of executable instructions. These threads of executable instructions may also share processor execution resources such as, for example, a page miss handler, or a hardware page walker, or a cache fill buffer, or some other execution resource.
A thread picker may choose one of several threads from which to issue instructions for execution. The thread picker may use a nominally round-robin algorithm so that all threads have equal access to the execution hardware. In some cases the thread picker may deviate from round-robin if the resources needed by a thread are temporarily unavailable. The thread picker may attempt to maintain fairness of resource allocation by dynamically computing resource thresholds for competing threads and filtering out those threads that have exceeded their resource thresholds. This may require the thread picker to store and maintain additional state information, for example thresholds, for shared resources and threads regardless of their actual shared resource use.
Some processor execution resources may require multiple clocks to service a request. For example, a hardware page walker may need tens of clock cycles to walk the page tables. This may give rise to a problem, in that once one thread has successfully sent a request to the shared resource, and the resource becomes busy, other threads that subsequently request access to the resource will be denied until the resource becomes available. If no provisions are made to ensure fairness, it is possible that the resource may be acquired again and again by the same thread, or alternatively by some subset of all of the threads. Consequently, this may permit a condition whereby a small number of threads hog a resource for long periods of time. Eventually, a live-lock detector may elevate priority levels to prevent a thread from experiencing complete starvation, but such techniques do not suffice to prevent an unfair allocation of processor execution resources from reoccurring.
To date, efficient logic and structures for fairly scheduling shared resources among contending threads of instructions in multithreaded processors have not been fully explored.